#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 510, M = 1e4 + 10;

int m, n, k;
int dist[N], backup[N]; // backup 存储上次 dist数组的值 保证不会被 可传递所影响

struct Edge{
    int a, b, w;
}edges[M];

int bellman_ford() {
    // 初始化最正无穷
    memset(dist, 0x3f3f3f3f, sizeof dist);
    // 初始化源点的距离为0
    dist[1] = 0;
    
    // 循环k次表示，从源点走 不超过 k条边的最短距离
    for (int i = 0; i < k; i ++) {
        // 每次需要备份上次dist数组
        memcpy(backup, dist, sizeof dist);
        // 遍历所有边
        for (int j = 0; j < m; j++) {
            // 更新所有边
            int a = edges[j].a, b = edges[j].b, w = edges[j].w;
            dist[b] = min(dist[b], backup[a] + w);
        }
    }
    
    if (dist[n] > 0x3f3f3f3f / 2) return -1;
    return dist[n];
}

int main()
{
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 0; i < m; i++) {
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        edges[i] = {a, b, w};
    }
    int t = bellman_ford();
    if (t == -1) printf("impossible");
    else printf("%d\n", t);
    return 0;
}